1. Field of the Invention
The present invention relates to a method and apparatus for address translation for translating a virtual address in a virtual memory system into a real address. More specifically, the present invention relates to a method and apparatus for translating a 64-bit virtual address into a real address.
Recently, a 64-bit configuration of data and addresses has been required with the demand for a higher operation speed of computer systems. To satisfy this demand, several methods of translating 64-bit virtual addresses into real addresses have been proposed, but an address translation method capable of easily maintaining compatibility with a 32-bit virtual address and also capable of rapid translation, has not yet been realized. Accordingly, an address translation method of a 64-bit virtual address, which can satisfy both compatibility with the 32-bit virtual address and high speed address translation, has been required.
2. Description of the Related Art
To begin with, a virtual memory system using a conventional virtual address of up to 32 bits will be explained. In the case of a virtual memory system using a 32-bit virtual address, for example, the virtual address comprises a segment number 104, a page index 62 and a page offset 64, as shown in FIG. 1.
Here, the segment number 104 represents the position where the virtual space, which is a variable-length block as a constituent element of a program, is divided into segment units, and the page index 62 represents the position where the segment region is divided into page units. Further, the page offset 64 represents the position inside the page region corresponding to the real space.
To translate a virtual address into a real address, a two-stage translation method which obtains the real address by retrieving a segment table 108 and a page table 112 as shown in FIG. 2, has ordinarily been used.
In other words, a base address of the segment table 108 is obtained from a segment table base register 106, and retrieval is then carried out by adding a segment number 104 of the virtual address as an offset to this base address to obtain a base address (PTB) 110 of the page table 112. Next, a page index 62 inside the virtual address is added as the offset to the base address 110 obtained from the segment table 108 so as to retrieve the page table 112 to obtain a page frame number (PFN) 114. Finally, the real address can be obtained by combining the page frame number 114 obtained from the page table 112 with the page offset 64 in the virtual address.
FIG. 3 shows the relationship between the virtual space and the real space according to the address translation method shown in FIG. 2. The virtual space 115 is first divided into segments 116-1, 116-2, . . . , and each segment is divided into pages 118-1 to 118-4 having a size corresponding to the real space 122, as typified by the segment 116-2.
An arbitrary address inside the virtual space 115 designated by 32 bits shown in FIG. 1, is translated into the real address by the two-stage translation using the segment table 108 and the page table 112, and represents a physical address in the real space 122 secured in a main storage unit (MSU).
Assuming hereby that the bit field of the virtual address is constituted by 10 bits for the segment number 104, 10 bits for the page index 62 and 12 bits for the page offset 64, the size of the page becomes 4 KB which is determined by the 12 bits of the page offset 64, and the segment table 108 and the page table 112 are respectively constituted by entry blocks of 1K determined by the 10 bits (2.sup.10 1K) of each of the segment number 104 and the page index 62 (refer to FIG. 2, entry #0 to entry #1K).
When such a conventional address translation method is applied to a virtual memory system using a virtual address exceeding 32 bits such as a 64-bit virtual address, for example, the bit construction becomes like the one shown in FIG. 4. In other words, it comprises 26 bits for the segment number 104, 26 bits for the page index 62 and 12 bits for the page offset 64 as shown in FIG. 4.
Here, the size of the page becomes 4KB determined by the 12-bit page offset 64, and the segment table 108 and the page table 112 are respectively constituted by entry blocks of 64M determined by 26 bits (2.sup.26 =64M) of each of the segment number 104 and the page index 62. Accordingly, the segment table and the page table become very large and the area they occupy in the real address space secured in the main storage unit becomes great. In other words, the real address space that can be practically used as the memory system becomes small.
One 64-bit address translation method for coping with such a problem is shown in FIG. 5. According to the address translation method shown in FIG. 5, the virtual address is divided into virtual address bits 124 and page offset bits 126. The virtual address bits 124 are translated into a hash address 130 by a hash generation circuit (Hash Gen.) 128, and a hash anchor table 132 is retrieved by this hash address 130.
A page frame table pointer (PFT) 134 is obtained from the hash anchor table 132, and when the page frame table 135 is retrieved by this pointer 134, a page frame table entry 136 can be obtained. This frame table entry (PFTE) 136 contains the virtual address, a page frame number and a link address.
Next, the virtual address bits 124 in the virtual address are compared with the virtual address inside the page frame entry table (PFTE) 136 and when they coincide with each other, the real address 26 can be obtained as the combination of the page frame number 142 with the page offset bits 126 in the virtual address. If they do not coincide, the next page frame table entry (PFTE) is obtained using the link address and a similar procedure is repeated until the coincident address can be found.
The virtual address bits 124 don't conform to the virtual address bits inside the page frame table entry (PFTE) 136, when the same hash addresses are generated even in the case where the virtual address bits are different from each other in the hash generation circuit 128. In this case, the virtual address bits 124 are stored in the page frame table entry (PFTE) corresponding to the link address generated in accordance with a predetermined rule.
FIG. 6 is an explanatory view showing the relationship between the virtual space and the real space in the address translation method shown in FIG. 5. In this case, the virtual space 146 is divided into pages 148-1, 148-2, . . . having a size corresponding to the real space 152.
An arbitrary virtual address inside this virtual space 146 is translated into the real address using the hash generation circuit 128, the hash anchor table 132 and the page frame table 135, and represents a physical address in the real space 152 secured in the main storage unit (MSU).
However, the conventional address translation method shown in FIG. 5 is devoid of the concept of "segment" which is higher by one stage than the page, as shown in the virtual space 146 in FIG. 6, and is greatly different from the virtual space 115 of the conventional 32-bit virtual address having the concept of segment for effecting two-stage table translation shown in FIG. 3. Here, the problem how to maintain compatibility arises.
Further, two tables, that is, the hash anchor table and the page frame table in the main storage unit, are retrieved before the comparison of the virtual addresses. This means that access to the main storage unit must be made twice, and another problem occurs in that a long time is necessary to confirm whether or not the address translation is correct.